package com.tingyuge.base.structrue.heap;

import java.util.*;
import java.util.PriorityQueue;

class Solution {



    public List<Integer> topKFrequent(int[] nums, int k) {

        TreeMap<Integer ,Integer> treeMap = new TreeMap<>();

        for (int num : nums) {
            if(treeMap.containsKey(num)){
                treeMap.put(num,treeMap.get(num)+1);
            }else{
                treeMap.put(num,1);
            }
        }
        System.out.println(treeMap.toString());

        PriorityQueue<Integer> qp = new PriorityQueue<>((a,b)->treeMap.get(a) - treeMap.get(b));

        for (Integer key : treeMap.keySet()) {
            //优先队列中,没有超过k就加入优先队列
            if(qp.size() < k){
                qp.add(key);
                //新的元素 比最小堆还要大的话.
            }else if(treeMap.get(key) > treeMap.get(qp.peek())){
                qp.remove();
                qp.add(key);
            }
        }

        List<Integer> list =  new LinkedList<>();

        while (!qp.isEmpty()){
            list.add(qp.remove());
        }
    return list;
    }

    public static void main(String[] args) {
      int[]   nums = {1,1,1,2,2,3,4,4,4,4,4};
        List<Integer> integers = new Solution().topKFrequent(nums, 3);
        System.out.println(integers.toString());
    }
}